package com.yangzhe.algorithm.c006;


import java.util.Arrays;

public class Code01_FindNumber {
    public static void main(String[] args) {
        // 随机长度范围
        int arrMax = 10;
        // 数组数量级
        int numberMax = 10;
        // 测试次数
        int testCount = 1;

        // 1. 数组长度
        System.out.println("测试开始");
        for (int i = 0; i < testCount; i++) {
            int searchNumber = 10;
            int randomArrayLength = (int) (Math.random() * arrMax) + 1;
            int[] arr = randomArray(randomArrayLength, numberMax);
            Arrays.sort(arr);
            boolean binarySearch = binarySearch(arr, searchNumber);
            boolean bruteForceSearch = bruteForceSearch(arr, searchNumber);
            if (binarySearch != bruteForceSearch) {
                System.out.println("测试失败");
            }
        }

        System.out.println("测试完成");
    }


    public static int[] randomArray(int length, int n) {
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            // 0 - 1 double 0 - n int
            arr[i] = (int) (Math.random() * n) + 1;
        }

        return arr;
    }


    public static int[] copyArray(int[] arr) {
        int[] arrCopy = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arrCopy[i] = arr[i];
        }

        return arrCopy;
    }

    /**
     * 二分搜索
     *
     * @param arr
     * @param number
     * @return
     */
    public static boolean binarySearch(int arr[], int number) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        // 左边界
        int l = 0;
        // 右边界
        int r = arr.length - 1;
        // 在没有越界（有数字）的情况下搜索
        while (l <= r) {
            // 中间点
            int m = (l + r) / 2;
            if (arr[m] == number) {
                return true;
            } else if (number > arr[m]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return false;
    }

    /**
     * 暴力搜索
     *
     * @return
     */
    public static boolean bruteForceSearch(int[] arr, int number) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == number) {
                return true;
            }
        }

        return false;
    }

}
